Homomorphic encryption is a form of encryption where a specific algebraic operation performed on the plaintext is equivalent to another (possibly different) algebraic operation performed on the ciphertext. Homomorphic encryption can be defined for both public-key (asymmetric) and private-key (symmetric) encryption. The original concept, called privacy homomorphism, was introduced by Rivest et al. in “On data banks and privacy homomorphisms,” Foundations of Secure Computation, pages 169-180 (1978), shortly after the invention of RSA, the public-key encryption algorithm. While encryption used in a number of industries, some unresolved difficulties in use of homomorphic encryption remain. In particular, the immediate downside aspect of encrypted data is that the data cannot be further processed (e.g. added, multiplied, searched), thus severely limiting any post-encryption computing of the ciphertext, especially by an external processing entity such as a cloud computing service.
Processing of this encrypted data has long been a problem without a practical and secure solution. While homomorphic encryption schemes are being developed to address this situation, aside from a few homomorphic encryption schemes involving almost exclusively asymmetric-key algorithms, there are no practical symmetric-key encryption solutions for the cloud today.
Gentry in “Fully homomorphic encryption using ideal lattices,” 41st ACM Symposium on Theory of Computing (STOC) (2009), used latticed-based cryptography to show the first fully homomorphic encryption (FHE) scheme for public-key cryptography. While this method creates an FHE scheme, the method remains impractical due to the complexity and large amount of computing involved. This complexity and the large amount of computing involved make the scheme's application, such as to a homomorphic search, not likely for the next 40 years, at least based on Moore's law. The scheme's applicability in the cloud storage and computing is also limited because the cloud uses prevalently private-key cryptography to store encrypted data.
Thus, existing technologies fail to provide an adequate solution to processing homomorphically-encrypted data in a cloud-computing environment, especially for data that is in motion. With the continual expansion of cloud computing, storing encrypted data using mostly symmetric-key encryption algorithms, having a practical homomorphic encryption method is critical in taking the cloud from a simple storage stage to having a real computing component that can process encrypted data and enable a series of cloud applications while retaining complete data privacy.
Therefore, there is a need for a way to provide data privacy in a cloud using homomorphic encryption while allowing the processing of such data.